BÀI TOÁN "BẢN ĐỒ CÁC VÙNG ĐẢO"Khi tiến hành khảo sát các đảo ở một vùng biển, người ta ghi kết quả khảo sát lại thành một bản đồ nhị phân, trong đó số 0 cho biết biển và số 1 là đất liền và được thể hiện trên 1 bàn cờ ở dạng kẻ lướiBài toán bản đồ các vùng đảo, là bài toán ứng dụng thực tế của việc tìm thành phần liên thông, là tiền đề cho việc thực hiện một số trò chơi nổi tiếng như: Minesweeper Dò mìn (trò chơi)

1.Ý Tưởng Thuật Toán

Khi làm việc với các dạng lưới kẻ ô như bàn cờ, bản đồ… thì người ta đưa ra khái niệm 2 ô kề nhau. Có nhiều loại kề nhau, như kề nhau theo bước đi con mã, theo đường chéo, theo lận cận 4, lân cận 8. Một đảo chính là một miền liên thông các lân cận 4 trên ma trận lưới.[2]

• Các ô màu vàng lần lượt là những ô kề nhau theo lân cận 4 và 8 với ô trung tâm (màu đen).
• Ô 1 và ô 2 (ô màu xanh) kề nhau theo lân cận 4 (và dĩ nhiên theo lân cận 8 luôn). Tương tự ô 2 và ô 3 cũng kề nhau theo lân cận 4. Ô 3 và ô 4 chỉ kề nhau theo lân cận 8, không theo lân cận 4. Ô 1 và ô 3 cũng kề nhau theo lân cận 8.
• Các ô 1, 2 và 3 tạo thành một miền liên thông 4 vì từ 1 đi được đến 2, từ 2 đi được đến 3 theo lân cận 4 (từ 3 không đến 4 được theo lân cận 4). Ô số bốn bản thân nó là một miền liên thông 4.
• Nếu xét theo liên thông 8 thì cả bốn ô (1, 2, 3, và 4) tạo thành một miền liên thông 8.